package com.ds.map_set.leetcode;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/10/8 15:12
 */
public class Num138_RandomList1 {
    public Node copyRandomList(Node head) {
        Node top; // 链表2的头节点
        if (head != null) {
            top = new Node(head.val);
        } else {
            return head;
        }
        Node temp1 = head.next;
        Node temp2 = top;
        /**
         * 第一轮循环先把链表复制到另一个链表中，后面再处理random指针，注意头指针保留，用temp1和temp2来做工作指针
         */
        while (temp1 != null) {
            Node temp = new Node(temp1.val);
            temp2.next = temp;
            temp2 = temp2.next;
            temp1 = temp1.next;
        }
        temp2=top; //重置链表2的头结点temp2指针
        temp1=head;
        while (temp2 != null){
            int offset = offset(head,temp1.random); //定义偏移量 相对于头节点的
            Node work = top;
            /**
             * 直接就是一个根据这个偏移量在链表2里面找到 并且指向它
             */
            for (int i = 0; i <offset ; i++) {
                work = work.next;
            }
            temp2.random = work;
            temp2 = temp2.next;
            temp1 = temp1.next;
        }
        return top;
    }

    /**
     * 传入链表1的某个结点的random结点，求出这个random是链表1的第几个结点
     * @param head
     * @param random
     * @return
     */
    private int offset(Node head,Node random) {
        int offset = 0;
        while (head!=random){
            head = head.next;
            offset++;
        }
        return offset;
    }
}


class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
